package com.liujiajun.lib;

import java.util.Stack;

public class BinaryTree {
    private Node root = null;
    public BinaryTree(int value){
        root = new Node(value);
        root.leftChild = null;
        root.rightChild = null;
    }

    /**
     * 查找
     * @param value
     * @return
     */
    private Node findKey(int value){
        Node current = root;
        while (true){
            if(value == current.value){
                return current;
            }else if(value < current.value){
                current = current.leftChild;
            }else if(value > current.value){
                current = current.rightChild;
            }
            if(current == null){
                return null;
            }
        }
    }

    /**
     * 插入
     * @param value
     * @return
     */
    public String insert(int value){
        String error = null;
        Node node = new Node(value);
        if(root == null){
            root = node;
            root.leftChild = null;
            root.rightChild = null;
        }else{
            Node current = root;
            Node parent = null;
            while (true){
                if(value < current.value){
                    parent = current;
                    current = current.leftChild;
                    if(current == null){
                        parent.leftChild = node;
                        break;
                    }
                }else if(value > current.value){
                    parent = current;
                    current = current.rightChild;
                    if(current == null){
                        parent.rightChild = node;
                        break;
                    }
                }else{
                    error = "having same value in binary tree";
                }
            }
        }
        return error;
    }

    /**
     * 中序遍历递归操作
     */
    public void inOrderTraverse(){
        System.out.println("中序遍历");
        inOrderTraverse(root);
        System.out.println();
    }
    public void inOrderTraverse(Node node){
        if(node == null){
            return ;
        }
        inOrderTraverse(node.leftChild);
        node.display();
        inOrderTraverse(node.rightChild);
    }
    /**
     * 中序遍历非递归操作
     * 1.对于任意节点current,若节点不为空则将节点压栈，并将左子树节点置为current，重复此操作，知道current为空位置
     * 2.若左子树为空，栈顶节点出栈，访问节点后将该节点的右子树置为current
     * 3.重复1、2步操作，知道current为空且栈内节点为空
     */
    public void inOrderByStack(){
        Stack<Node> stack = new Stack<Node>();
        Node current = root;
        while (current != null ||!stack.isEmpty()){
            while (current !=null){
                stack.push(current);
                current = current.leftChild;
            }
            if (!stack.isEmpty()){
                current = stack.pop();
                current.display();
                current = current.rightChild;
            }
        }
    }

    /**
     * 前序遍历递归操作
     * 1.访问这个节点
     * 2.调用自身来遍历节点的左子树
     * 3.调用自身来遍历节点的右子树
     */
    public void preOrderTraverse(){
        preOrderTraverse(root);
        System.out.println();
    }
    public void preOrderTraverse(Node node){
        if (node == null){
            return;
        }
        node.display();
        preOrderTraverse(node.leftChild);
        preOrderTraverse(node.rightChild);
    }

    /**
     * 前序遍历非递归操作
     */
    public void preOrderByStack(){
        Stack<Node> stack = new Stack<Node>();
        Node current = root;
        while (current !=null || !stack.isEmpty()){
            while (current != null){
                stack.push(current);
                current.display();
                current = current.leftChild;
            }
            if(!stack.isEmpty()){
                current = stack.pop();
                current = current.rightChild;
            }
        }
        System.out.println();
    }

    /**
     * 后序遍历递归操作
     */
    public void postOrderTraverse(){
        postOrderTraverse(root);
        System.out.println();
    }
    public void postOrderTraverse(Node node){
        if(node == null){
            return ;
        }
        postOrderTraverse(node.leftChild);
        postOrderTraverse(node.rightChild);
        node.display();
    }


    /**
     * 后序遍历非递归操作
     * 1.对于任意节点current,若该节点不为空则访问该节点后再将节点压栈，并将左子树置为current,重复此操作，知道current为空
     * 2.若左子树为空，取栈顶节点的右子树，如果右子树为空或右子树刚刚访问过，则访问该节点，并将preNode置为该节点
     * 3.重复1.2步骤，知道current为空且栈节点为空
     */
    public void postOrderByStack(){
        Stack<Node> stack = new Stack<Node>();
        Node current = root;
        Node preNode = null;
        while(current != null || !stack.isEmpty()){
            while (current != null){
                stack.push(current);
                current = current.leftChild;
            }
            if(!stack.isEmpty()){
                current = stack.peek().rightChild;
                if(current == null || current == preNode){
                    current = stack.pop();
                    current.display();
                    preNode = current;
                    current = null;
                }
            }
        }
    }

    /**
     * 得到最小值
     * @return
     */
    public int getMinValue(){
        Node current = root;
        while (true){
            if(current.leftChild == null){
                return current.value;
            }
            current = current.leftChild;
        }
    }

    /**
     * 删除
     * @param value
     * @return
     */
    public boolean delete(int value){
        return true;
    }

}
